package com.atguigui.leetcode1;

/**
 * 1234.替换子串得到平衡字符串
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/2/13 9:19
 */
public class P1234ReplaceTheSubstringForBalancedString {
    public static void main(String[] args) {
        Solution solution = new P1234ReplaceTheSubstringForBalancedString().new Solution();
        // TO TEST
    }

    class Solution {
        public int balancedString(String s) {

            int[] cnt = new int[26];
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                cnt[idx(c)]++;
            }

            int partial = s.length() / 4;
            int res = s.length();
            if (check(cnt, partial)) {
                return 0;
            }
            for (int l = 0, r = 0; l < s.length(); l++) {
                while (r < s.length() && !check(cnt, partial)) {
                    cnt[idx(s.charAt(r))]--;
                    r++;
                }
                if (!check(cnt, partial)) {
                    break;
                }
                res = Math.min(res, r - l);
                cnt[idx(s.charAt(l))]++;
            }

            return res;
        }

        //判断 QWER 出现次数是否满足partial数
        private boolean check(int[] cnt, int partial) {
            if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial || cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
                return false;
            }
            return true;
        }

        private int idx(char c) {
            return c - 'A';
        }
    }
}
